
#include "terminator.h"
#include "tools/string_util.h"

#include <fstream>
#include <algorithm>
#include <list>
#include <sstream>

#include <stdio.h>
#include <ctype.h>

#include "logging.h"

#define DEBUG   false

Terminator::Terminator()
    : mDictionaryPath("dict.txt")
    , mWorkMode(WORKMODE_SIMPLE)
    , mWordCount(0)
{
}

Terminator::~Terminator()
{
}

void Terminator::setDictionary(const char * path)
{
    mDictionaryPath = path;
}

void Terminator::setWorkMode(WorkMode mode)
{
    mWorkMode = mode;
}

void Terminator::readIgnoreTable()
{
    if (mIgnoreTablePath.empty()) {
        return;
    }

    std::ifstream    ifr(mIgnoreTablePath.c_str());
    if (!ifr) {
        return;
    }
    std::string line;
    while (std::getline(ifr, line, '\n')) {
        line = tools::trim(line);
        if (line.empty())
            continue;
        std::transform(line.begin(), line.end(), line.begin(), tolower);
        mIgnoreTable.push_back(line);
    }
    ifr.close();
    // printf("read %lu words from ignore table.\n", mIgnoreTable.size());
}

bool Terminator::isInIgnoreTable(std::string word)
{
    if (mIgnoreTable.empty())
        return false;
    if (std::find(mIgnoreTable.begin(), mIgnoreTable.end(), word) == mIgnoreTable.end())
        return false;
    // GLOG() << "ignore: " << word;
    return true;
}

int Terminator::readDictionary(std::string words)
{
    std::ifstream    ifr(mDictionaryPath.c_str());

    if (!ifr) {
        fprintf(stderr, "open %s failed.\n", mDictionaryPath.c_str());
        return -1;
    }
    v.clear();
    std::string line;
    int     ignored_count = 0;
    while (std::getline(ifr, line, '\n')) {
        line = tools::trim(line);
        if (line.empty())
            continue;
        std::transform(line.begin(), line.end(), line.begin(), tolower);

        if (isInIgnoreTable(line)) {
            ignored_count++;
            continue;
        }
        if (!canSpell(line, words)) {
            ignored_count++;
            continue;
        }
        v.push_back(line);
    }
    ifr.close();
    // printf("read %lu words from %s. %d ignored\n", v.size(), mDictionaryPath.c_str(), ignored_count);

    if (DEBUG) {
        std::vector<std::string>::iterator  it;
        for (it = v.begin(); it != v.end(); it++) {
            printf("%s ", (*it).c_str());
        }
        printf("\n---------------------\n");
    }
    return v.size();
}

bool Terminator::isNewResult(std::string result)
{
    std::vector<std::string>  l1;
    std::vector<std::string>  l2;

    tools::split(result, l1);
    std::sort(l1.begin(), l1.end(), tools::string_sort_proc);
    
    std::list<std::string>::iterator    it;
    std::vector<std::string>::iterator    it1;
    std::vector<std::string>::iterator    it2;
    for (it = result_table.begin(); it != result_table.end(); it++) {
        std::string res = *it;
        tools::split(res, l2);
        std::sort(l2.begin(), l2.end(), tools::string_sort_proc);
        
        for (it1 = l1.begin(), it2 = l2.begin(); it1 != l1.end() && it2 != l2.end(); it1++, it2++) {
            // GLOG() << "*it1 = " << *it1 << ", *it2 = " << *it2;
            if (*it1 != *it2)
                break;
        }
        if (it1 == l1.end() && it2 == l2.end()) {
            return false;
        }
    }
    result_table.push_back(result);
    return true;
}

int Terminator::start(std::string words)
{
    readIgnoreTable();
    if (mWorkMode == WORKMODE_SIMPLE) {
        return deal(words);
    } else {
        char c = 'a';
        for (unsigned int i = 0; i < words.length(); i++) {
            if (mReplaceMap.find(words[i]) != mReplaceMap.end())
                continue;
            mReplaceMap[words[i]] = c++;
        }

        std::map<char, char>::iterator  it;
        std::map<char, char>::iterator  it1;
        // ScopeTrace(x);
        while (true) {

            // unique
            for (it = mReplaceMap.begin(); it != mReplaceMap.end(); it++) {
                it1 = it;
                it1++;
                for (; it1 != mReplaceMap.end(); it1++) {
                    if (it->second == it1->second) {
                        break;
                    }
                }
                if (it1 != mReplaceMap.end())
                    break;
            }
            if (it == mReplaceMap.end()) {
                // map
                if (DEBUG) {
                    for (it1 = mReplaceMap.begin(); it1 != mReplaceMap.end(); it1++) {
                        printf("%c => %c, ", it1->first, it1->second);
                    }
                    printf("\n");
                }

                // deal.
                std::string newword;
                for (unsigned int i = 0; i < words.length(); i++) {
                newword += mReplaceMap[words[i]];
                }
                deal(newword);
            }

            it = mReplaceMap.begin();
            while (it != mReplaceMap.end()) {
                if (it->second == 'z') {
                    mReplaceMap[it->first] = 'a';
                    it++;
                } else {
                    mReplaceMap[it->first] = it->second + 1;
                    break;
                }
            }
            if (it == mReplaceMap.end())
                break;

        }

        return 0;
    }
}

int Terminator::deal(std::string words)
{
    // result_table.clear();
    if (readDictionary(words) <= 0) {
        return -1;
    }

    unsigned int len = words.length();

    std::vector<int>    depth_table;
    depth_table.resize(len);
    unsigned int i, j, k;
    for (i = 0; i < len; i++) {
        depth_table[i] = 0;
    }

    std::list<int>  stack;

    i = 0;
    while (true) {
        for (; i < v.size(); i++) {
            std::string w = v[i];
            std::string chars;

            for (j = 0; j < len; j++) {
                if (depth_table[j] == 0)
                    chars += words[j];
            }

            if (!canSpell(w, chars)) {
                // GLOG() << "cannot spell: " << w <<" from " << chars;
                continue;
            }
            // GLOG() << "can spell '" << w <<"' from '" << chars << "'";

            // mark depth.
            for (j = 0; j < w.length(); j++) {
                for (k = 0; k < len; k++) {
                    if (depth_table[k] == 0 && words[k] == w[j]) {
                        depth_table[k] = (int)stack.size() + 1;
                        break;
                    }
                }
            }

            stack.push_back(i);

            // debug
            if (DEBUG) {
                GLOG() << "stack.push " << i;
                std::list<int>::iterator it;
                printf("stack: ");
                for (it = stack.begin(); it != stack.end(); it++) {
                    printf("%d ", *it);
                }
                printf("\n");

                printf("%s\n", words.c_str());
                for (j = 0; j < len; j++) {
                    printf("%d", depth_table[j]);
                }
                printf("\n");
            }

            break;
        }

        // get result.
        for (j = 0; j < len; j++) {
            if (depth_table[j] == 0)
                break;
        }
        if (j >= len && (mWordCount <= 0 || (int)stack.size() == mWordCount)) {
            std::string result;
            std::list<int>::iterator it;
            for (it = stack.begin(); it != stack.end(); it++) {
                int n = *it;
                result += v[n] + std::string(" ");
            }
            result = tools::trim(result);
            if (isNewResult(result)) {
                printf("%s\n", result.c_str());

                printf("\t%s\n\t", words.c_str());
                for (j = 0; j < len; j++) {
                    printf("%d", depth_table[j]);
                }
                printf("\n");
            }

        }

        // no more result.
        if (i >= v.size() || j >= len || (mWordCount > 0 && (int)stack.size() > mWordCount)) {
            if (stack.empty())
                break;
            i = stack.back();
            stack.pop_back();
            i++;
            for (j = 0; j < len; j++) {
                if (depth_table[j] >= (int)stack.size() + 1)
                    depth_table[j] = 0;
            }

            // debug
            if (DEBUG) {
                GLOG() << "stack.pop " << i;
                std::list<int>::iterator it;
                printf("stack: ");
                for (it = stack.begin(); it != stack.end(); it++) {
                    printf("%d ", *it);
                }
                printf("\n");
                printf("%s\n", words.c_str());
                for (j = 0; j < len; j++) {
                    printf("%d", depth_table[j]);
                }
                printf("\n");
            }

        } else {
            i = 0;
        }
    } // while true;

    // printf("find %lu result.\n", result_table.size());

    return 0;
}

bool Terminator::canSpell(std::string word, std::string chars)
{
    std::vector<bool>   t;
    int i;
    int len = chars.length();
    t.resize(len);
    for (i = 0; i < len; i++) {
        t[i] = false;
    }

    unsigned int j;
    for (j = 0; j < word.length(); j++) {
        int k;
        for (k = 0; k < len; k++) {
            if (!t[k]) {
                if (chars[k] == word[j]) {
                    t[k] = true;
                    break;
                }
            }
        }
        if (k >= len)
            return false;
    }
    return true;
}












